package com.ls.day17;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ：xxx
 * @description：TODO
 * @date ：2021/4/2 10:37
 */
public class PermuteUnique {

    public static void main(String[] args) {
        permuteUnique(new int[]{1,1,2});
    }

    static List<List<Integer>> ans = new ArrayList<>();
    static List<Integer> tem = new ArrayList<>();
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] visit = new boolean[nums.length];
        def(nums,visit);
        return ans;
    }

    public static void def(int[] nums,boolean[] visit){
        if (tem.size()==nums.length){
            List<Integer> a = new ArrayList<>(tem);
            ans.add(a);
            return;
        }
        for (int i=0;i<nums.length;i++){
            if (!visit[i]){
                visit[i]=true;
                tem.add(nums[i]);
                def(nums,visit);
                visit[i]=false;
                tem.remove(tem.size()-1);
                int j=i+1;
                while (j<nums.length && nums[j]==nums[i])j++;
                i=j-1;
            }
        }
    }
}
